https://leetcode.cn/problems/lru-cache/description/

class LRUCache {
public:
    LRUCache(int capacity) 
        :_capacity(capacity)
    {
    }
    
    int get(int key) {
        auto hashit=_HashMap.find(key);
        //找到
        if(hashit!=_HashMap.end())
        {
            auto it=hashit->second;
           _list.splice(_list.begin(),_list ,it);

           return it->second; 
        }
        else
        {
            return -1;
        }

    }
    
    void put(int key, int value) {
        auto hashit=_HashMap.find(key);
        if(hashit==_HashMap.end())
        {
            //检查扩容
            if(_capacity==_HashMap.size())
            {
                //尾删
                auto back=_list.back();
                _HashMap.erase(back.first);
                _list.pop_back();
            }

            //新增
            _list.push_front(make_pair(key,value));
            _HashMap[key]=_list.begin();
        }
        else{
            auto it=hashit->second;
            it->second=value;
           _list.splice(_list.begin(),_list ,it); 
        }
    }

private:
    size_t _capacity;
    unordered_map<int ,list<pair<int,int>>::iterator> _HashMap;
    list<pair<int ,int>> _list;
};